package Topological;
import java.util.*;
/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-14
 * Time:17:21
 * Text：210. 课程表2
 */
public class Text2 {
    public int[] findOrder(int n, int[][] prerequisites) {
        //记录出度结点
        HashMap<Integer,List<Integer>> map=new HashMap<>();
        //记录每个结点的入读数目
        int[] array=new int[n];

        for(int[] arr:prerequisites){
            int l=arr[1],r=arr[0];
            if(!map.containsKey(l)){
                map.put(l,new ArrayList<>());
            }
            map.get(l).add(r);
            array[r]++;
        }
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<n;i++){
            if(array[i]==0){
                q.add(i);
            }
        }
        int[] ret=new int[n];
        int left=0;
        while(!q.isEmpty()){
            int a=q.poll();
            ret[left++]=a;
            for(int c:map.getOrDefault(a,new ArrayList<>())){
                array[c]--;
                if(array[c]==0){
                    q.add(c);
                }
            }
        }
        for(int ab:array){
            if(ab!=0) return new int[0];
        }
        return ret;
    }
}
